package top.humbleyuan.bfs;

import java.util.LinkedList;
import java.util.Queue;

/**
 * @Author HumbleYuan
 * @Date 2020/5/18 20:31
 * @Des 岛屿数量
 * @pro 待补充并查集方法
 */
public class LeetCode_200 {
    public static void main(String[] args) {
        char[][] nums = {{'1','1','0','0','0'},{'1','1','0','0','0'},{'0','0','1','0','0'},{'0','0','0','1','1'}};

        if(nums == null || nums.length == 0 || nums[0].length == 0) {
            System.out.println(0);
            return;
        }

        boolean[][] flag = new boolean[nums.length][nums[0].length];

        int count = 0;

        // 向左向右拓展，用栈存之前的点
        for (int i = 0; i < nums.length; i++) {
            int x, y;
            for (int j = 0; j < nums[i].length; j++) {

                if(nums[i][j] == '1') {
                    count ++;
                    Queue<String> queue = new LinkedList<>();

                    nums[i][j] = '0';
                    queue.offer(i + "," + j);
                    while (!queue.isEmpty()) {
                        String[] loc = queue.poll().split(",");
                        int a = Integer.valueOf(loc[0]);
                        int b = Integer.valueOf(loc[1]);

                        // 上下左右
                        x = a;
                        y = b + 1;
                        if(y < nums[i].length && nums[x][y] == '1') {
                            nums[x][y] = '0';
                            queue.offer(x + "," + y);
                        }

                        x = a;
                        y = b - 1;
                        if(y >= 0 && nums[x][y] == '1') {
                            nums[x][y] = '0';
                            queue.offer(x + "," + y);
                        }

                        x = a - 1;
                        y = b;
                        if(0 <= x && nums[x][y] == '1') {
                            nums[x][y] = '0';
                            queue.offer(x + "," + y);
                        }

                        x = a + 1;
                        y = b;
                        if(x < nums.length && nums[x][y] == '1') {
                            nums[x][y] = '0';
                            queue.offer(x + "," + y);
                        }
                    }
                }
            }
        }

        System.out.println(count);
    }
}
